1. Field of the Invention
The present invention relates to information security techniques that use prime number generation.
2. Related Art
Data communication that uses computer and communication techniques has become pervasive in recent years. Secret communication or digital signature techniques are used in such data communication.
Secret communication techniques allow communication to be performed without the communicated content being revealed to third parties. Digital signature techniques, meanwhile, enable a receiver to verify whether the communicated content is valid or whether the information is from the stated sender.
1. Public Key Cryptography
Such secret communication or digital signature techniques use a cryptography called public key encryption. Public key encryption provides a convenient method for managing the separate encryption keys of many users, and so has become a fundamental technique for performing communication with a large number of users. In secret communication based on public key encryption, different keys are used for encryption and decryption, with the decryption key being kept secret and the encryption key being made public. Hereinafter, a decryption key which is kept secret is called a “secret key”, whereas an encryption key which is made public is called a “public key”.
The RSA (Rivest-Shamir-Adelman) cryptosystem is one type of public key cryptography. The RSA cryptosystem relies on the computational difficulty of factoring an integer, for its security. The prime factorization problem is the following. When integer n=p×q is given where p and q are primes, find p and q. Here, “x” represents normal multiplication.
The prime factorization problem is described in detail in T. Okamoto & K. Ohta (1990) Encryption, Zero Knowledge Proofs, and Number Theory, published by Kyoritsu, pp. 144–151.
(RSA Cryptosystem Using the Prime Factorization Problem)
The RSA cryptosystem that uses the prime factorization problem is explained below.
(1) Generation of Keys
A public key and a secret key are generated in the following manner.
(a) Select two large primes p and q at random, and form their product n=p×q.
(b) Find the least common multiple of p−1 and q−1, i.e., L=LCM(p−1,q−1).
(c) Select integer e at random which is relatively prime to and smaller than L:1≦e≦L−1, GCD(e,L)=1
where GCD(e,L) denotes the greatest common divisor of e and L.
(d) Calculate d=e−1 mod L.
The pair of integers n and e is the public key, whereas the pair of integers n and d is the secret key.
(2) Generation of Ciphertext
Plaintext m is encrypted using public key (n,e), to obtain ciphertext c:c=me mod n(3) Generation of Decrypted Text
Ciphertext c is decrypted using secret key (n,d), to obtain decrypted text m′:m′=cd mod n
Here,
                              m          ′                =                ⁢                              c            d                    ⁢          mod          ⁢                                          ⁢          n                                        =                ⁢                                            (                              m                e                            )                        d                    ⁢          mod          ⁢                                          ⁢          n                                        =                ⁢                              m            **                          (                              e                ×                d                ⁢                                                                  ⁢                mod                ⁢                                                                  ⁢                L                            )                                ⁢                                          ⁢          mod          ⁢                                          ⁢          n                                        =                ⁢                              m            1                    ⁢          mod          ⁢                                          ⁢          n                                        =                ⁢                  m          ⁢                                          ⁢          mod          ⁢                                          ⁢          n                    
Therefore, decrypted text m′ matches plaintext m.
Note that in this specification the operator “**” represents exponentiation, so that A**x=Ax where A is multiplied by itself x times.
The RSA cryptosystem is described in detail in T. Okamoto & H. Yamamoto (1997) Modern Encryption, published by Sangyo Tosho, pp. 110–113.
2. Related Art 1—Probabilistic Prime Generation Algorithm
To generate a public key in the above RSA cryptosystem that uses the prime factorization problem, prime generation is performed. Prime generation is described in detail in A. J. Menezes, P. C. van Oorschot, & S. A. Vanstone (1997) Handbook of Applied Cryptography, published by CRC Press, pp. 145–154.
A probabilistic prime generation algorithm as a conventional technique is explained below. The probabilistic prime generation algorithm applies the Rabin-Miller test to determine the primality of a number. The Rabin-Miller test is described in detail in A. J. Menezes, P. C. van Oorschot, & S. A. Vanstone (1997) Handbook of Applied Cryptography, published by CRC Press, pp. 138–140. The Rabin-Miller test determines a number, which has a high probability of being prime, as a prime. This does not mean that the number is definitely prime.
Suppose natural number x and small primes L1, L2, . . . , Ln are given beforehand. As one example, L1, L2, . . . , Ln are 2, 3, 5, 7.
The probabilistic prime generation algorithm generates a prime by repeating the following steps.
(step 1) Assign natural number x to variable N as an initial value.
(step 2) Find the smallest number that is not divisible by any of L1, L2, . . . , Ln, among numbers larger than variable N. Assign the number to variable N.
(step 3) Test the primality of variable N. The primality test here is done by repeating the Rabin-Miller test ten times. If variable N passes the primality test, output variable N as a prime. If variable N fails the primality test, return to step 2 and repeat the procedure until a prime is output.
Here, finding the number that is not divisible by any of the small primes 2, 3, 5, 7 in step 2 has the effect of reducing the number of times the primality test is performed. In other words, step 2 limits the numbers to test for primality, to those numbers which are not divisible by any of 2, 3, 5, 7. There are 47 numbers where 2xx+1 mod 210 is not divisible by any of 2, 3, 5, 7. Accordingly, if the numbers to test for primality are limited to those which are not divisible by any of 2, 3, 5, 7, the number of times the primality test is performed can be reduced by 47/210.
On the other hand, even if variable N obtained in step 2 is a composite number (i.e. not a prime), variable N has at most ¼ chance of passing the Rabin-Miller test. Which is to say, even if variable N is composite, it may pass the Rabin-Miller test. Thus, the above probabilistic prime generation algorithm can generate a prime only probabilistically, and not definitely.
(Computational Complexity of the Probabilistic Prime Generation Algorithm)
Computational complexity of generating a prime using the above probabilistic prime generation algorithm is explained next. Here, computational complexity is measured as the number of modular exponentiations.
According to the above probabilistic prime generation algorithm, the Rabin-Miller test is repeated ten times for a number which may be prime. The following calculates the average number of times the Rabin-Miller test is performed for one composite number.
Let Pi be a probability of performing the ith test. Then a probability Pi+1 of performing the (i+1)th test is no greater than the product of the probability, Pi, of performing the ith test and the probability, ¼, of passing this ith test. Which is to say, the probability of performing the (i+1)th test isPi+1≦Pi×¼
Since the first test is definitely performed, the probability of the first test is 1, that is, P1=1. Accordingly,Pi≦(¼)**(i−1)
One modular exponentiation is performed for one Rabin-Miller test. The above probabilistic prime generation algorithm conducts at most ten Rabin-Miller tests in step 3. Therefore, the average number of modular exponentiations performed for one composite number is
                    ∑                  i          =          1                10            ⁢              P        i              ⪯                  ∑                  i          =          1                10            ⁢                        (                      1            /            4                    )                **                  (                      i            -            1                    )                      =  1.33
In general, when N is arbitrarily chosen, a probability of N being a prime is about 1/(ln N). This means that one prime can be found when (ln N) primality tests are conducted on average. Here, (ln N) is a natural logarithm of N. Since the numbers which are divisible by any of 2, 3, 5, 7 have been excluded beforehand, the average number of primality tests to be conducted to find one prime can be reduced by φ(2×3×5×7)/210=48/210. Here, φ(2×3×5×7) is the number of numbers, among the natural numbers less than 210, which are relatively prime to the small primes 2, 3, 5, 7. Hence the number of numbers which are tested for primality until one prime is found, that is, the total number of numbers which are judged as being composite and a number which is lastly judged as being prime, is 8/35×(ln N)
Since the last number is prime, the number of composite numbers which undergo the primality test is( 8/35×(ln N))−1
This being so, the number of modular exponentiations performed to find one prime is no greater than
            (                                    8            /            35                    ×                      (                          ln              ⁢                                                          ⁢              N                        )                          -        1            )        ×          (                        ∑                      i            =            1                    10                ⁢                  1          /                      (                          4              **                              (                                  n                  -                  1                                )                                      )                              )        +  10
on average. For example, when N is 512 bits, the number of modular exponentiations is at most 116.8. On the other hand, if the primality test is not limited to the numbers which are not divisible by any of 2, 3, 5, 7, that is, if all numbers are subjected to the primality test, then the number of modular exponentiations performed to find one prime is no greater than
            (                        (                      ln            ⁢                                                  ⁢            N                    )                -        1            )        ×          (                        ∑                      i            =            1                    10                ⁢                  1          /                      (                          4              **                              (                                  n                  -                  1                                )                                      )                              )        +  10
on average. When N is 512 bits, the number of modular exponentiations is at most 481.9. Thus, the number of modular exponentiations can be reduced to about ¼ according to the related art 1. However, this method, has the aforementioned problem of not being able to generate a definite prime.
3. Related Art 2—Deterministic Prime Generation Algorithm
A deterministic prime generation method using the Maurer algorithm that can generate a prime with an absolute certainty is explained below. The Maurer algorithm is described in detail in A. J. Menezes, P. C. van Oorschot, & S. A. Vanstone (1997) Handbook of Applied Cryptography, published by CRC Press, pp. 152–153.
The deterministic prime generation algorithm generates a prime by repeating the following steps. Here, prime q whose bit size is demoted by lenq is given in advance.
(step 1 ) Select random number R of (lenq−1) bits, where the first bit of random number R is set to be definitely 1.
(step 2 ) Calculate number N according to the following equation:N=2×q×R+1
(step 3 ) See whether the following first and second criteria are met, and judge number N as being prime if both are met. Otherwise, judge number N as not being prime.2N−1=1 modN  (First Criterion)GCD(22R−1,N)=1  (Second Criterion)
If number N is judged as being prime, output number N as a prime. Otherwise, return to step 1 and repeat the procedure until a prime is output.
This primality test is called the Pocklington test, and described in detail in A. J. Menezes, P. C. van Oorschot, & S. A. Vanstone (1997) Handbook of Applied Cryptography, published by CRC Press, p. 144.
According to the Pocklington test, if q in the equation N=2×q×R+1 is prime and the first and second criteria are met, N is definitely prime. This enables primality to be deterministically judged, with it being possible to generate a definite prime.
Thus, the Maurer deterministic prime generation algorithm generates prime N whose size is 2×lenq, based on prime q whose size is lenq.
In other words, to generate a prime of a predetermined length using the Maurer deterministic prime generation algorithm, the generation of a prime no greater than the predetermined length needs to be repeatedly performed. For example, to generate a 512-bit prime, first a 16-bit prime is generated based on an 8-bit prime which has been given beforehand. Next, a 32-bit prime is generated based on the 16-bit prime, and then a 64-bit prime is generated based on the 32-bit prime. The prime generation is repeated in this way, as a result of which a 512-bit prime is obtained.
Note here that the above second criterion can be replaced by22R≠1 mod N(Computational Complexity of the Deterministic Prime Generation Algorithm)
Computational complexity of generating a prime using the Maurer deterministic prime generation algorithm is as follows.
Here, computational complexity is measured as the number of modular exponentiations for a 512-bit number. Which is to say, consider the case where a 512-bit prime is generated using a 256-bit prime.
Generally, when arbitrarily selecting positive integer R, a probability of positive integer R being prime is about 1/(ln R). This being so, the number of times the Pocklington test is conducted to find a 512-bit prime can be estimated at ln 2512. Since the primality test is conducted only for odd numbers in the related art 2, the number of Pocklington tests is (ln 2512)/2.
A probability of meeting the first criterion is at most ¼, which is equal to the probability of passing the Rabin-Miller test. Accordingly, the number of modular exponentiations performed for one composite number is no greater than 1+¼. Meanwhile, the number of modular exponentiations performed for one prime is 2.
Therefore, the number of 512-bit modular exponentiations performed to generate a 512-bit prime from a 256-bit prime is no greater than(1+¼) ((ln 2512)/2−1)+2=222. 6
Likewise, in the case where a 256-bit prime is generated from a 128-bit prime, the number of Pocklington tests is (ln 2256)/2. Hence the number of 256-bit modular exponentiations performed to generate a 256-bit prime is no greater than(1+¼) ((ln 2256)/2−1)+2
Computational complexity of modular exponentiation depends on the modulus N, and is the order of N3. Therefore, eight 256-bit modular exponentiations can be regarded as being equivalent to one 512-bit modular exponentiation.
When other cases such as generating a 128-bit prime from a 64-bit prime are considered in the same way, the total computational complexity of the related art 2 can be measured as the number of 512-bit modular exponentiations.
Here, computational complexity of generating a 16-bit or 32-bit prime is much smaller than computational complexity of generating a 64-bit, 128-bit, 256-bit, or 512-bit prime, so that the computational complexity for 16-bit and 32-bit primes can be ignored. This being so, when expressed as the number of 512-bit modular exponentiations, the total computational complexity of the related art 2 is no greater than(1+¼)×{((ln 264)/2−1)/512+((ln 2128)/2−1)/64+((ln 2256)/2−1)/8+((ln 2512)/2−1)}+2( 1/512+ 1/64+⅛+1)=237.4
The computational complexity of the related art 2 is at least twice as much as the computational complexity of the related art 1 which is no greater than 116.8. Thus, the related art 2 takes more computational complexity than the related art 1, though it can generate a prime deterministically.
In short, prime generation has the following problem. If an algorithm with small computational complexity is employed, primes cannot be generated deterministically. On the other hand, if an algorithm that can generate primes deterministically is employed, computational complexity increases.